#ifndef LEETCODE_TREE_H
#define LEETCODE_TREE_H

#include <vector>
#include <stack>
#include <iostream>
#include <queue>
#include <functional>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

//递归法构建二叉树
TreeNode *creatTree(vector<int> nums, int index) {
    //判断是否为空
    if (nums[index] == '#')
        return NULL;

    //创建新结点
    TreeNode *root = new TreeNode;
    root->val = nums[index];
    int n = nums.size();

    //设置左右指针
    if (index * 2 <= n)
        root->left = creatTree(nums, index * 2);	//找到左孩子
    else
        root->left = NULL;
    if (index * 2 + 1 <= n)
        root->right = creatTree(nums, index * 2 + 1);	//找到右孩子
    else
        root->right = NULL;

    return root;
}


void preorder_print_tree(TreeNode* root) {
    if(!root) return;
    std::cout << root->val << " ";
    preorder_print_tree(root->left);
    preorder_print_tree(root->right);
}

//! 递归前序遍历
std::vector<int> preorderTraversal(TreeNode* root) {
    std::vector<int> res;
    if(!root) return res;
    std::stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        res.push_back(node->val);
        if(node->right) st.push(node->right);
        if(node->left) st.push(node->left);
    }

    return res;
}

//! 递归中序遍历
std::vector<int> inorderTraversal(TreeNode* root) {
    std::vector<int> res;
    if(!root) return res;
    std::stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        if(node != nullptr) {
            if(node->right) st.push(node->right);
            st.push(node);
            st.push(nullptr);
            if(node->left) st.push(node->left);
        }else {
            node = st.top();
            st.pop();
            res.push_back(node->val);
        }
    }
    return res;
}

//! 递归后序遍历
std::vector<int> postorderTraversal(TreeNode* root) {
    std::vector<int> res;
    if(!root) return res;
    std::stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        res.push_back(node->val);
        if(node->left) st.push(node->left);
        if(node->right) st.push(node->right);
    }

    std::reverse(res.begin(), res.end());
    return res;
}

//! 层序遍历
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    std::queue<TreeNode*> nodes;
    if(!root) return res;
    nodes.push(root);
    while(!nodes.empty()) {
        vector<int> num;
        int sz = nodes.size();
        for(int i=0; i<sz; i++) {
            TreeNode* node = nodes.front();
            num.push_back(node->val);
            nodes.pop();
            if(node->left) nodes.push(node->left);
            if(node->right) nodes.push(node->right);
        }
        res.push_back(num);
    }
    return res;
}

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>> res;
    std::queue<TreeNode*> nodes;
    if(!root) return res;
    nodes.push(root);
    while(!nodes.empty()) {
        vector<int> num;
        int sz = nodes.size();
        for(int i=0; i<sz; i++) {
            TreeNode* node = nodes.front();
            num.push_back(node->val);
            nodes.pop();
            if(node->left) nodes.push(node->left);
            if(node->right) nodes.push(node->right);
        }
        res.push_back(num);
    }
    reverse(res.begin(), res.end());
    return res;
}

//! 226. 翻转二叉树
TreeNode* invertTree(TreeNode* root) {
    if (!root || (!root->left && !root->right)) {
        return root;
    }
    TreeNode* right_node = nullptr;
    TreeNode* left_node = nullptr;
    if (root->left) {
        right_node = invertTree(root->left);
    }
    if (root->right) {
        left_node = invertTree(root->right);
    }
    root->right = right_node;
    root->left = left_node;
    return root;
}

//! 101.对称二叉树
bool isSymmetric(TreeNode* root) {
    std::function<bool(TreeNode*, TreeNode*)> func = [&func](TreeNode* l, TreeNode* r){
        if(!l && !r) {
            return true;
        } else if(l && r && l->val == r->val) {
            return func(l->right, r->left) && func(l->left, r->right);
        } else {
            return false;
        }
    };
    return func(root->left, root->right);
}


//! 104. 二叉树的最大深度
int maxDepth(TreeNode* root) {
    if(!root) return 0;
    std::queue<TreeNode*> nodes;
    int depth = 0;
    nodes.push(root);
    while(!nodes.empty()) {
        int sz = nodes.size();
        for(int i=0; i<sz; i++) {
            TreeNode* node = nodes.front();
            nodes.pop();
            if(node->left) nodes.push(node->left);
            if(node->right) nodes.push(node->right);
        }
        depth++;
    }
    return depth;
}

//! 104. 二叉树的最大深度（递归）
int maxDepth1(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth1(root->left), maxDepth1(root->right));
}

//! 111. 二叉树的最小深度（递归）
int minDepth(TreeNode* root) {
    if(!root) return 0;
    if(!root->left) return 1 + minDepth(root->right);
    if(!root->right) return 1 + minDepth(root->left);
    return 1 + min(minDepth(root->left), minDepth(root->right));
}

//! 111. 二叉树的最小深度
int minDepth1(TreeNode* root) {
    if(!root) return 0;
    std::queue<TreeNode*> nodes;
    int depth = 0;
    nodes.push(root);
    while(!nodes.empty()) {
        int sz = nodes.size();
        depth++;
        for(int i=0; i<sz; i++) {
            TreeNode* node = nodes.front();
            nodes.pop();
            if(node->left) nodes.push(node->left);
            if(node->right) nodes.push(node->right);
            if(!node->left && !node->right) {
                return depth;
            }
        }
    }
    return depth;
}
//! 222. 完全二叉树的节点个数
int countNodes(TreeNode* root) {
    if(!root) return 0;
    std::queue<TreeNode*> nodes;
    int count = 0;
    nodes.push(root);
    while(!nodes.empty()) {
        int sz = nodes.size();
        count += sz;
        for(int i=0; i<sz; i++) {
            TreeNode* node = nodes.front();
            nodes.pop();
            if(node->left) nodes.push(node->left);
            if(node->right) nodes.push(node->right);
        }
    }
    return count;
}

//! 222. 完全二叉树的节点个数（递归）
int countNodes1(TreeNode* root) {
    if (root == NULL) return 0;
    return 1 + countNodes1(root->left) + countNodes1(root->right);
}

//！ 110.平衡二叉树
bool isBalanced(TreeNode* root) {
    if (!root) return true;
    if(abs(maxDepth(root->left) - maxDepth(root->right)) <= 1) {
        return isBalanced(root->left) && isBalanced(root->right);
    } else {
        return false;
    }
}

vector<string> binaryTreePaths(TreeNode* root) {
    std::function<void(TreeNode*, string, vector<string>&)> func = [&func](TreeNode* node, string path, vector<string> &res) {
        if(!node) return;
        if(!node->left && !node->right) {
            res.push_back(path);
            return;
        }
        path.append(std::to_string(node->val));
        if(node->left) {
            func(node->left, path + "->", res);
        }
        if(node->right) {
            func(node->right, path + "->", res);
        }
    };

    vector<string> res {};
    func(root, "", res);
    return res;
}

//! 404.左叶子之和
int sumOfLeftLeaves(TreeNode* root) {
    int res = 0;
    if(!root) return res;
    std::stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        if(node->right) st.push(node->right);
        if(node->left) {
            st.push(node->left);
            if(!node->left->left && !node->left->right) {
                res += node->left->val;
            }
        }
    }
    return res;
}

//! 404.左叶子之和（递归）
int sumOfLeftLeaves1(TreeNode* root) {
    if (root == NULL) return 0;
    int leftValue = 0;
    if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {
        leftValue = root->left->val;
    }
    return leftValue + sumOfLeftLeaves1(root->left) + sumOfLeftLeaves1(root->right);
}

int findBottomLeftValue(TreeNode* root) {
    int res;
    std::queue<TreeNode*> nodes;
    nodes.push(root);
    while(!nodes.empty()) {
        res = nodes.front()->val;
        int sz = nodes.size();
        for(int i=0; i<sz; i++) {
            TreeNode* node = nodes.front();
            nodes.pop();
            if(node->left) nodes.push(node->left);
            if(node->right) nodes.push(node->right);
        }
    }
    return res;
}

bool hasPathSum(TreeNode* root, int targetSum) {
    std::function<bool(TreeNode*, int)> func = [targetSum, &func](TreeNode* node, int sum) {
        if(!node) return false;
        sum += node->val;
        if(!node->left && !node->right) {
            if(sum == targetSum) {
                return true;
            } else {
                return false;
            }
        }
        return func(node->left, sum) || func(node->right, sum);
    };
    return func(root, 0);
}

//! 106. 从中序与后序遍历序列构造二叉树
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    if (inorder.empty() || postorder.empty()) return nullptr;
    int root_val = postorder.back();
    int i;
    for (i=0; i < inorder.size(); i++) {
        if(inorder[i] == root_val) {
            break;
        }
    }
    vector<int> left_inorder(inorder.begin(), inorder.begin() + i);
    vector<int> right_inorder(inorder.begin() + i + 1, inorder.end());

    postorder.pop_back();

    vector<int> left_postorder(postorder.begin(), postorder.begin() + left_inorder.size());
    vector<int> right_postorder(postorder.begin() + left_inorder.size(), postorder.end());
    TreeNode* root = new TreeNode(root_val);
    root->left = buildTree(left_inorder, left_postorder);
    root->right = buildTree(right_inorder, right_postorder);
    return root;
}

//! 654. 最大二叉树
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    if (nums.empty()) return nullptr;
    auto max_iter = std::max_element(nums.begin(), nums.end());
    TreeNode* root = new TreeNode(*max_iter);
    vector left_nums(nums.begin(), max_iter);
    vector right_nums(max_iter + 1, nums.end());
    root->left = constructMaximumBinaryTree(left_nums);
    root->right = constructMaximumBinaryTree(right_nums);
    return root;
}

//! 617. 合并二叉树
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    TreeNode* root;
    if (root1 && root2) {
        root = new TreeNode(root1->val + root2->val);
        root->left = mergeTrees(root1->left, root2->left);
        root->right = mergeTrees(root1->right, root2->right);
    } else if(!root1 && root2) {
        root = root2;
        root->left = root2->left;
        root->right = root2->right;
    } else if(!root2 && root1) {
        root = root1;
        root->left = root1->left;
        root->right = root1->right;
    } else {
        return nullptr;
    }
    return root;
}

//! 700. 二叉搜索树中的搜索
TreeNode* searchBST(TreeNode* root, int val) {
    if (!root) return nullptr;
    if(val > root->val) {
        return searchBST(root->right, val);
    } else if(val < root->val) {
        return searchBST(root->left, val);
    } else if(val == root->val) {
        return root;
    }
}

//! 98. 验证二叉搜索树 : 中序遍历后为递增数组
bool isValidBST(TreeNode* root) {
    std::vector<int> res;
    std::stack<TreeNode*> nodes;
    nodes.push(root);
    int prev;
    bool is_root = true;
    while (!nodes.empty()) {
        TreeNode* node = nodes.top();
        nodes.pop();
        if(node) {
            if(node->right) nodes.push(node->right);
            nodes.push(node);
            nodes.push(nullptr);
            if(node->left) nodes.push(node->left);
        } else {
            node = nodes.top();
            nodes.pop();
            if (!is_root) {
                if (node->val <= prev) {
                    return false;
                }
            } else {
                is_root = false;
            }
            prev = node->val;
        }

    }
    return true;
}

//! 530. 二叉搜索树的最小绝对差
int getMinimumDifference(TreeNode* root) {
    std::stack<TreeNode*> nodes;
    nodes.push(root);
    int prev;
    int dif = INT_MAX;
    bool is_first = true;
    while (!nodes.empty()) {
        TreeNode* node = nodes.top();
        nodes.pop();
        if(node) {
            if(node->right) nodes.push(node->right);
            nodes.push(node);
            nodes.push(nullptr);
            if(node->left) nodes.push(node->left);
        } else {
            node = nodes.top();
            nodes.pop();
            if (!is_first) {
                dif = min(dif, node->val - prev);
            } else {
                is_first = false;
            }
            prev = node->val;
        }

    }
    return dif;
}

//! 530. 二叉搜索树的最小绝对差
int getMinimumDifference_(TreeNode* root) {
    int res = INT_MAX;
    TreeNode* prev = nullptr;

    std::function<void(TreeNode*)> func = [&func, &res, &prev](TreeNode* cur) {
        if (!cur) return ;
        func(cur->left);
        if(prev) {
            res = min(res, cur->val - prev->val);
        }
        prev = cur;
        func(cur->right);
    };

    func(root);
    return res;
}

//! 501. 二叉搜索树中的众数
vector<int> findMode(TreeNode* root) {
    std::vector<int> res;
    std::stack<TreeNode*> nodes;
    nodes.push(root);
    int prev;
    int max_count = 1;
    int cur_count = 1;
    bool is_first = true;
    while (!nodes.empty()) {
        TreeNode* node = nodes.top();
        nodes.pop();
        if(node) {
            if(node->right) nodes.push(node->right);
            nodes.push(node);
            nodes.push(nullptr);
            if(node->left) nodes.push(node->left);
        } else {
            node = nodes.top();
            nodes.pop();
            if (!is_first) {
                if(node->val == prev) {
                    cur_count++;
                } else {
                    if(max_count < cur_count) {
                        max_count = cur_count;
                        res.clear();
                        res.push_back(prev);
                    } else if (max_count == cur_count) {
                        res.push_back(prev);
                    }
                    cur_count = 1;
                }
            } else {
                is_first = false;
            }
            prev = node->val;
        }

    }
    if(max_count < cur_count) {
        max_count = cur_count;
        res.clear();
        res.push_back(prev);
    } else if (max_count == cur_count) {
        res.push_back(prev);
    }
    return res;
}

//! 501. 二叉搜索树中的众数
vector<int> findMode_(TreeNode* root) {
    vector<int> res;
    TreeNode* prev = nullptr;
    int cur_count = 1;
    int max_count = 1;

    std::function<void(TreeNode*)> func = [&func, &res, &prev, &cur_count, &max_count](TreeNode* cur) {
        if (!cur) return ;
        func(cur->left);
        if(prev) {
            if(prev->val == cur->val) {
                cur_count++;
            } else {
                if(max_count < cur_count) {
                    max_count = cur_count;
                    res.clear();
                    res.push_back(prev->val);
                } else if (max_count == cur_count) {
                    res.push_back(prev->val);
                }
                cur_count = 1;
            }
        }
        prev = cur;
        func(cur->right);
    };

    func(root);
    if(max_count < cur_count) {
        max_count = cur_count;
        res.clear();
        res.push_back(prev->val);
    } else if (max_count == cur_count) {
        res.push_back(prev->val);
    }
    return res;
}

//! 236. 二叉树的最近公共祖先
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* res = nullptr;

    std::function<bool(TreeNode*, TreeNode*, TreeNode*)> isAncestor = [](TreeNode* root, TreeNode* p, TreeNode* q) {
        std::queue<TreeNode*> nodes;
        nodes.push(root);
        bool flag_p = false, flag_q = false;
        while(!nodes.empty()) {
            int sz = nodes.size();
            for(int i=0; i<sz; i++) {
                TreeNode* node = nodes.front();
                nodes.pop();
                if (node == p) flag_p = true;
                if (node == q) flag_q = true;
                if (flag_p && flag_q) {
                    return true;
                }
                if(node->left) nodes.push(node->left);
                if(node->right) nodes.push(node->right);
            }
        }
        return false;
    };

    std::queue<TreeNode*> nodes;
    nodes.push(root);
    while(!nodes.empty()) {
        int sz = nodes.size();
        bool flag = false;
        for(int i=0; i<sz; i++) {
            TreeNode* node = nodes.front();
            nodes.pop();
            if(node->left) nodes.push(node->left);
            if(node->right) nodes.push(node->right);
            if (!flag) {
                if (isAncestor(node, p, q)) {
                    res = node;
                    flag = true;
                }
            }
        }
        flag = false;
    }
    return res;
}

//! 236. 二叉树的最近公共祖先
TreeNode* lowestCommonAncestor_(TreeNode* root, TreeNode* p, TreeNode* q) {
    // 找到p、q中的一个就返回
    if(root == p || root == q || !root) return root;
    TreeNode* left = lowestCommonAncestor_(root->left, p, q);
    TreeNode* right = lowestCommonAncestor_(root->right, p, q);
    if(left && right) return root;
    if(!left) return right;
    return left;
}

//! 235. 二叉搜索树的最近公共祖先
TreeNode* lowestCommonAncestor__(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root->val > p->val && root->val > q->val) {
        return lowestCommonAncestor__(root->left, p, q);
    } else if(root->val < p->val && root->val < q->val) {
        return lowestCommonAncestor__(root->right, p, q);
    } else {
        return root;
    }
}

//! 701. 二叉搜索树中的插入操作
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    TreeNode* node = root;
    TreeNode* parent;
    while(node) {
        parent = node;
        if (node->val > val) {
            node = node->left;
        } else if (node->val < val) {
            node = node->right;
        }
    }
    if (parent->val > val) {
        parent->left = new TreeNode(val);
    } else {
        parent->right = new TreeNode(val);
    }
    return root;
}

//! 450. 删除二叉搜索树中的节点
TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return nullptr;
    TreeNode* node = root;
    TreeNode* root_parent = new TreeNode(root->val - 1);
    TreeNode* parent = nullptr;
    root_parent->left = root;
    while(node) {
        if (node->val < key) {
            parent = node;
            node = node->right;
        } else if(node->val > key) {
            parent = node;
            node = node->left;
        } else {
            break;
        }
    }
    if (node) {
        if(!parent) {
            parent = root_parent;
        }
        bool isleftchild = parent->left == node ? true : false;
        if(node->left && !node->right) {
            if(isleftchild) {
                parent->left = node->left;
            } else {
                parent->right = node->left;
            }
            delete node;
        } else if(!node->left && node->right) {
            if(isleftchild) {
                parent->left = node->right;
            } else {
                parent->right = node->right;
            }
            delete node;
        } else if(!node->left && !node->right) {
            if(isleftchild) {
                parent->left = nullptr;
            } else {
                parent->right = nullptr;
            }
            delete node;
        } else if(node->left && node->right) { // 被删除节点两边都有child
            if(node->right->left) {
                TreeNode* node_new = node->right; // 最小节点的父节点
                while(node_new->left->left) {
                    node_new = node_new->left;
                }
                node->val = node_new->left->val;
                node_new->left = node_new->left->right;
            } else {
                TreeNode* node_new = node->right;
                node_new->left = node->left;
                if(isleftchild) {
                    parent->left = node_new;
                } else {
                    parent->right = node_new;
                }
                delete node;
            }
        }
    }
    return root_parent->left;
}

//! 669. 修剪二叉搜索树
TreeNode* trimBST(TreeNode* root, int low, int high) {
    if(!root) return nullptr;
    if(root->val < low) return trimBST(root->right, low, high);
    if(root->val > high) return trimBST(root->left, low, high);
    root->left = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);
    return root;
}

//! 108. 将有序数组转换为二叉搜索树
TreeNode* sortedArrayToBST(vector<int>& nums) {
    if(nums.empty()) return nullptr;
    auto iter = nums.begin() + nums.size() / 2;
    TreeNode* root = new TreeNode(*iter);
    vector<int> left_nums(nums.begin(), iter);
    vector<int> right_nums(iter + 1, nums.end());
    root->left = sortedArrayToBST(left_nums);
    root->right = sortedArrayToBST(right_nums);
    return root;
}

//! 538. 把二叉搜索树转换为累加树
TreeNode* convertBST(TreeNode* root) {
    if(!root) return nullptr;
    stack<TreeNode*> nodes;
    nodes.push(root);
    vector<TreeNode*> res;

    int pre = 0;

    while (!nodes.empty()) {
        TreeNode* node = nodes.top();
        nodes.pop();
        if(node) {
            if(node->left) nodes.push(node->left);
            nodes.push(node);
            nodes.push(nullptr);
            if(node->right) nodes.push(node->right);
        } else {
            node = nodes.top();
            nodes.pop();
            // 处理中节点
            node->val += pre;
            pre = node->val;
        }
    }

    return root;
}
//! 100. 相同的树
bool isSameTree(TreeNode* p, TreeNode* q) {
    if(!p && !q) return true;
    if(p && q && p->val == q->val) {
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    } else {
        return false;
    }
}

//! 129. 求根节点到叶节点数字之和
int sumNumbers(TreeNode* root) {
    int res = 0;
    function<void(TreeNode*, int)> dfs = [&dfs, &res](TreeNode* root, int cur_sum){
        cur_sum = cur_sum * 10 + root->val;
        if(!root->left && !root->right) {
            res += cur_sum;
            return ;
        }
        if(root->left) dfs(root->left, cur_sum);
        if(root->right) dfs(root->right, cur_sum);
    };

    dfs(root, 0);
    return res;
}
#endif //LEETCODE_TREE_H
